#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解题思路：
首先思考递归树应该如何画，当取出一个元素放入path中树就要向下递归取下一个元素,若当前不想取第一个元素而想要取第二个元素则需要使用
for循环加回溯进行取第二个元素,这里需要注意，由于求的是子集所以一个分支上面的所有节点都是结果，全部都要放进result结果集中
第二个解题思路更加直观，对于求子集问题可以考虑取每个元素的状态，每个元素可以取或者不取两种状态，所以此时构建另一种递归树
这样树形结构是每层有nums个节点，且深度为nums
*/
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> nums,int index)
{
    //将递归的每一个节点都放入result,若递归到最后一个元素时，要先将path放入result中才进行终止条件的判断
    result.push_back(path);
    //递归终止条件
    if(index>=nums.size())
        return;
    for(int i=index;i<nums.size();i++)
    {
        path.push_back(nums[i]);
        backtracking(nums,i+1);
        path.pop_back();
    }
}
//第二种方法实现
void backtracking2(vector<int> nums,int index)
{
    if(index==nums.size())
    {
        result.push_back(path);
        return;
    }
    path.push_back(nums[index]);
    backtracking2(nums,index+1);
    path.pop_back();
    backtracking2(nums,index+1);       
}   
vector<vector<int>> subsets(vector<int>& nums) {
    backtracking2(nums,0);
    return result;
}
int main()
{
    cout<<"enter number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    result = subsets(nums);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}